package com.mid;

import java.util.Stack;

/**
 * Created by Lxk on 2020/1/27.
 */
public class Solution91 {

    //todo finish
    private static int count = 0;

    private void findSolution(char[] chs, int pos, Stack<String> strings) {
        if (pos >= chs.length) {
            count++;
        } else {
            //放一个
            StringBuffer sb = new StringBuffer();
            sb.append(chs[pos]);
            if (Integer.valueOf(sb.toString()) > 0 && Integer.valueOf(sb.toString()) < 27) {
                strings.push(sb.toString());
                findSolution(chs, pos + 1, strings);
                strings.pop();
            }
            if (pos + 1 >= chs.length) {
                return;
            }
            //放两个
            if (sb.toString().equals("0")) {
                return;
            }
            sb.append(chs[pos + 1]);
            if (Integer.valueOf(sb.toString()) < 27 && Integer.valueOf(sb.toString()) > 0) {
                strings.push(sb.toString());
                findSolution(chs, pos + 2, strings);
            }
        }
    }

    public int numDecodings(String s) {
        count = 0;
        if (s.charAt(0) == '0') {
            return count;
        }
        if ("0".equals(s)) {
            return count;
        }
        char[] chs = s.toCharArray();
        Stack<String> stack = new Stack<>();
        findSolution(chs, 0, stack);
        return count;
    }

    public static void main(String[] args) {
        Solution91 solution91 = new Solution91();
        System.out.println(solution91.numDecodings("9371597631128776948387197132267188677349946742344217846154932859125134924241649584251978418763151253"));
    }

}
